package JzOffer.jz43;

import java.util.LinkedList;
import java.util.Queue;

class Solution01 {
	public static void main(String[] args){
		
	}
}

class CBTInserter {
	private TreeNode root;
	
	public CBTInserter(TreeNode root){
		this.root = new TreeNode();
		this.root.val = root.val;
		this.root.left = root.left;
		this.root.right = root.right;
	}

	public int insert(int v){
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(this.root);
		//利用队列层次遍历二叉树
		while(!queue.isEmpty()){
			TreeNode curNode = queue.poll();
			if(curNode.left != null){
				queue.offer(curNode.left);
			} else {
				//左子树不存在，插入
				curNode.left = new TreeNode(v);
				return curNode.val;
			}
			if(curNode.right != null){
				queue.offer(curNode.right);
			} else {
				//右子树不存在，插入
				curNode.right = new TreeNode(v);
				return curNode.val;
			}
		}
		return v;
	}

	public TreeNode get_root(){
		return this.root;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(){}

	TreeNode(int val){
		this.val = val;
	}

	TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}
